/**
 * https://leetcode.cn/problems/cherry-pickup-ii/submissions/590295731/
 * 1463.摘樱桃
 * difficulty 2024.12.30
 * 记忆化搜索
 */

class Solution {
public:
    int n;
    int m;
    auto dfs(vector<vector<int>>& grid,vector<vector<vector<int>>>& dp,int i,int j,int k){
        if(i==n||j<0||j>=m||k<0||k>=m){
            return 0;
        }
        int &ans=dp[i][j][k];
        if(ans!=-1){
                return ans;
        }
        for(int t=j-1;t<=j+1;++t){
            for(int d=k-1;d<=k+1;++d){
                ans=max(ans,dfs(grid,dp,i+1,t,d));
            }
        }
        ans+=grid[i][j]+(k!=j?grid[i][k]:0);
        return ans;
    }
    int cherryPickup(vector<vector<int>>& grid) {
        n=grid.size();
        m=grid[0].size();
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(m,vector<int>(m,-1)));
        return dfs(grid,dp,0,0,m-1);
    }
};